__author__ = 'st316'
'''
You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
'''


class Solution:
    # @param n, an integer
    # @return an integer
    def climbStairs(self, n):
        r = [0, 1, 2]
        if n < 3:
            return r[n]
        for i in xrange(3, n + 1):
            r.append(r[i - 1] + r[i - 2])
        return r[-1]


if __name__ == '__main__':
    s = Solution()
    print s.climbStairs(3)